import java.util.*;

public class Test {
    /*
    题目1：子集
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>(); // 解集
        lists.add(new ArrayList<Integer>()); // 首先将空集加入解集中
        for(int i = 0; i < nums.length; i++){
            int size = lists.size(); // 当前子集数
            for(int j = 0; j < size; j++){
                List<Integer> newList = new ArrayList<>(lists.get(j));// 拷贝所有子集
                newList.add(nums[i]); // 向拷贝的子集中加入当前数形成新的子集
                lists.add(newList); // 向lists中加入新子集
            }
        }
        return lists;
    }

    public static void main1(String[] args) {
        int[] arr = {1,2,3};
        subsets(arr);
    }

    /*
    题目2：x 的平方根
     */
    public int mySqrt(int x) {
        // 二分查找算法
        if(x < 1){
            return 0;
        }

        long left = 1, right = x;

        while(left < right){
            long mid = left + (right - left + 1)/2;
            if(mid * mid <= x){
                left = mid;
            }else if(mid * mid > x){
                right = mid - 1;
            }
        }
        return (int)left;

    }

    /*
    题目3：搜索插入位置
     */
    public int searchInsert1(int[] nums, int target) {
        // 划分成 小于 t 以及 大于等于 t 的情况！
        int n = nums.length;
        int left = 0, right = n - 1;

        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        // 特判一下插入到最尾部的情况
        if(nums[left] < target) return left + 1;
        return left;
    }

    // 也可以划分成 小于等于 t 以及 大于 t 的情况！
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;

        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid - 1;
            }
        }

        if(nums[left] < target) return left + 1;
        return left;
    }

    /*
    题目 4：山峰数组的峰顶索引
     */
    public int peakIndexInMountainArray(int[] arr) {
        // 这个题只有一个峰！可以用 二分查找
        // 对于左半部分来说，前一个的值总比后一个的小！
        // 对于右半部分来说，前一个总比后一个大！
        int n = arr.length;

        int left = 0, right = n - 1;

        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] >= arr[mid - 1]){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return left;

    }

    /*
    题目 5：寻找峰值
     */
    public int findPeakElement(int[] nums) {
        int n = nums.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] < nums[mid + 1]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }

    /*
    题目6：寻找旋转排序数组中的最小值
     */
    // 数组可以分成两部分
    // 以数组最后一个值为基准
    // 左半部分的值都 大于 这个基准
    // 右半部分的值 小于等于 这个基准
    public int findMin(int[] nums) {
        int n = nums.length;

        int left = 0, right = n - 1;

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[n - 1]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }

    /*
    题目7：0~n-1中缺失的数字
     */
    // 左半部 ：值与下标相同
    // 右半部：值比下标多 1
    public int missingNumber(int[] nums) {
        int n = nums.length;

        int left = 0, right = n - 1;

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == mid){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[right] == right){
            return right + 1;
        }else{
            return right;
        }
    }

    /*
    题目 8：前缀和
     */
    


}
